package 中等.栈;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可
 * 能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回
 * true；否则，返回 false 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/validate-stack-sequences
 */
public class 验证栈序列_946 {

    public static void main(String[] args) {

        System.out.println(validateStackSequences(new int[]{2, 1, 0}, new int[]{1, 2, 0}));

    }

    public static boolean validateStackSequences(int[] pushed, int[] popped) {
        Deque<Integer> stack = new ArrayDeque<>();
        int pushIdx = 0, popIdx = 0;
        while (pushIdx < pushed.length || popIdx < popped.length) {
            // 将所有能抵消掉的全部抵消
            while (!stack.isEmpty() && popIdx < popped.length && stack.peekFirst() == popped[popIdx]) {
                stack.pollFirst();
                popIdx++;
            }
            // 不能抵消才推入一个元素
            if (pushIdx < pushed.length) {
                stack.addFirst(pushed[pushIdx]);
                pushIdx++;
            }
            // 推入的元素已经全部推完，但是仍然有未弹出并且不能弹出的元素时，失败
            if (pushIdx >= pushed.length && popIdx < popped.length &&
                    stack.peekFirst() != popped[popIdx]) {
                return false;
            }
        }
        return true;
    }

}
